package com.arithmeticEveryDay.greed;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/*

4 5
0 1 8
0 2 3
0 3 1
3 2 1
2 1 1


7 12
0 1 4
0 2 6
0 3 6
1 4 7
1 2 1
2 4 6
2 5 4
3 2 2
3 5 5
4 6 6
5 4 1
5 6 8






9 28
0 1 4
1 0 4
0 7 8
7 0 8
1 2 8
2 1 8
7 8 7
8 7 7
7 6 1
6 7 1
1 7 11
7 1 11
2 8 2
8 2 2
2 3 7
3 2 7
2 5 4
5 2 4
8 6 6
6 8 6
6 5 2
5 6 2
3 4 9
4 3 9
3 5 14
5 3 14
5 4 10
4 5 10





 */

public class ShortestPath {
    
    static InOut5 io = new InOut5();
    static final int MAX_WEIGHT = 0x0000ffff; // 表示无穷大的值
    int vertexCount;
    int edgeCount;
    int[][] graph;
    
    public ShortestPath(int vertexCount, int edgeCount, int[][] graph) {
        this.vertexCount = vertexCount;
        this.edgeCount = edgeCount;
        this.graph = graph;
    }
    
    /*
    
    单源最短路径问题是在给定的带权有向图或无向图中，找到从指定源结点到所有其它结点的最短路径，
    通常用来解决有向图。
    dijkstra算法解决单源最短路径问题，保证边为非负数，步骤如下：
    1、数据结构：
    distance数组存放每个点到源点的最短路径；
    previous数组存放每个点在最短路径下的前一个结点
    ensured数组存放每个点的最短路径是否确定下来的布尔值
    2、初始化：
    默认0索引为源点索引
    distance中0索引位置值为0，其它位置初始值为∞
    previous中初始值均为-1
    ensured中0索引位置值为true，其余位置初始值都为false
    3、遍历从已确定最短路径的顶点出发
    初始情况已确定的顶点只有0，那么找0到其它顶点的距离，
    并把距离与distance中原有的值对比，小于则distance对应值更新为找到的新距离，
    同时previous记录此距离路径下的上一个结点
    另外还需在这一轮找到的距离中选出一个最短的距离distance(0, i)，
    因为边为非负数，所以可以确定对应顶点i已经找到了到0的最短路径
    至此本轮遍历结束，进入下一轮遍历
    初始位置已确定的顶点为0和i，找0和i顶点到其它顶点的距离，
    同时previous记录此距离路径下的上一个结点
    并把距离与distance中原有的值对比，小于则distance对应值更新为找到的新距离，同时更新
    另外还需在这一轮找到的距离中选出一个最短的距离distance(0, j)，
    因为边为非负数，所以可以确定对应顶点j已经找到了到0的最短路径
    至此本轮遍历结束，进入下一轮遍历
    
    
         1        1
    1 <----- 2 <---- 3
    ↑        ↑       ↑
     \       |      /
      \      |     /
     8 \    3|    / 1
        \    |   /
         \   |  /
          \  | /
             0
    
    
     */
    public void dijkstra() {
        int[] distance = new int[vertexCount];
        int[] previous = new int[vertexCount];
        boolean[] ensured = new boolean[vertexCount];
        // 初始化
        for (int i = 1; i < vertexCount; i++) {
            distance[i] = graph[0][i];
            if (distance[i] == MAX_WEIGHT) {
                previous[i] = i;
            } else {
                previous[i] = 0;
            }
        }
        previous[0] = -1;
        ensured[0] = true;
        
        // 外部for循环控制循环次数，0已确定，剩余最多确定vertexCount-1个顶点的最短路径
        for (int i = 0; i < vertexCount; i++) {
            // 内部第一个for循环，遍历未访问的顶点，找到当前离源点最近的顶点，直接比较distance即可
            // 前提是distance先更新完，初始状态算做第一次更新，所以可以用distance来比较
            int t = -1;
            for (int j = 0; j < vertexCount; j++) {
                if (!ensured[j] && (t == -1 || distance[j] < distance[t])) {
                    t = j;
                }
            }
            // t仍为-1说明已经没有未访问顶点了
            if (t == -1) {
                break;
            }
            // 此时t的最短路径已确定
            io.out.println(t);
            ensured[t] = true;
            // 由于t的最短路径已经确定，所以在t的基础上更新其它点的distance
            for (int j = 0; j < vertexCount; j++) {
                if (!ensured[j] && graph[t][j] < MAX_WEIGHT) {
                    int newDistance = distance[t] + graph[t][j];
                    if (newDistance < distance[j]) {
                        distance[j] = newDistance;
                        previous[j] = t;
                    }
                }
            }
            io.out.println(Arrays.toString(distance));
            io.out.println(Arrays.toString(previous));
            io.out.println(Arrays.toString(ensured));
        }
        io.out.println(Arrays.toString(distance));
        io.out.println(Arrays.toString(previous));
        io.out.println(Arrays.toString(ensured));
    }

    public static void main(String[] args) {
        int vertexCount = io.nextInt();
        int edgeCount = io.nextInt();
        int[][] graph = new int[vertexCount][vertexCount];
        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                if (i != j) {
                    graph[i][j] = MAX_WEIGHT;
                }
            }
        }
        for (int i = 0; i < edgeCount; i++) {
            graph[io.nextInt()][io.nextInt()] = io.nextInt();
        }
        ShortestPath s = new ShortestPath(vertexCount, edgeCount, graph);
        s.dijkstra();
        io.out.flush();
    }

}
class InOut5 {
    BufferedReader br;
    StringTokenizer tok;
    PrintWriter out;
    InOut5() {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }
    public boolean hasNext() {
        while (tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                return false;
            }
        }
        return true;
    }
    public String next() {
        if (hasNext()) {
            return tok.nextToken();
        }
        return null;
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
    
}

